1175F - The Number of Subpermutations - CodeForces Solution

#include<bits/stdc++.h>
#define M 5001
using namespace std;
mt19937_64 rnd(time(0));
int n,a[300001];
long long h[300001],base[300001],pre[300001];
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
void solve(){
	int n; n=read();
	for(int i = 1; i <= n; ++i){
		a[i]=read();
		h[i] = rnd();
		base[i] = base[i - 1] ^ h[i];
	}
	int ans = 0;
	for(int i = 1, j = 1; i <= n; ++i){
		pre[i] = pre[i - 1] ^ h[a[i]];
		if(a[i] == 1) j = 1, ++ans;
		else{
			j = max(j, a[i]);
			if(i >= j && (pre[i] ^ pre[i - j]) == base[j]) ++ans;
		}
	}
	reverse(a + 1, a + n + 1);
	for(int i = 1, j = 1; i <= n; ++i){
		pre[i] = pre[i - 1] ^ h[a[i]];
		if(a[i] == 1) j = 1;
		else{
			j = max(j, a[i]);
			if(i >= j && (pre[i] ^ pre[i - j]) == base[j]) ++ans;
		}
	}
	printf("%d\n",ans);
}
int main()
{
	solve();
	return 0;
}